package main

type IntSlice []int

func (this IntSlice) Less(i, j int) bool {
	return this[i] < this[j]
}

func (this IntSlice) Swap(i, j int) {
	this[i], this[j] = this[j], this[i]
}

func SortInts(a []int) {
	SortSlice(a, 0, len(a)-1)
}

// return (mid)
func doPivot(a IntSlice, lo, hi int) int {
	p := lo
	for i := lo; i < hi; i++ {
		if a.Less(i, hi) {
			a.Swap(i, p)
			p++
		}
	}
	a.Swap(hi, p)
	return p
}

func SortSlice(a IntSlice, lo, hi int) {
	if lo >= hi {
		return
	}
	p := doPivot(a, lo, hi)
	if p > lo {
		SortSlice(a, lo, p-1)
	}
	if p < hi {
		SortSlice(a, p+1, hi)
	}
}
